package com.hyper_yang.algorithmRecord;

// leetcode 42 接雨水 https://leetcode.cn/problems/trapping-rain-water/description/
public class LeetCode_42 {
    /*
        给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，
        计算按此排列的柱子，下雨之后能接多少雨水。
     */

    // 方法一: 动态规划 - myself
    public static int trap1(int[] height) {
        int n = height.length;
        // 对于数组中的每一根柱子，我们都需要知道他左边最高的柱子的高度和右边最高柱子的高度
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        // 初始化 leftMax
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        // 初始化 rightMax
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
        }
        // 计算总雨水量
        int sumRainVolume = 0;
        for (int i = 0; i < n; i++) {
//            int currRainVolume = Math.min(leftMax[i],rightMax[i]) - height[i]; // 没关系，因为计算左右时最低高度就是自身柱子高度，所以最小值为 0，不会是负数
//            int currRainVolume = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]); // 为了写法上严谨，还是判断下不要计算‘负体积雨水’
            sumRainVolume += Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
        }
        return sumRainVolume;
    }

    // 方法二: 双指针 - myself 加深对双指针的理解
    public static int trap(int[] height) {
        int sumRainVolume = 0;
        int left = 0;
        int right = height.length - 1;
        int leftMax = height[left];
        int rightMax = height[right];
        while (left < right) {
            if (leftMax < rightMax) { // rightMax 在 left 移动时是 “足够 ”的，不需要是真正的 rightHighest。
                // 移动左指针，试图增加左边高度
                left++;
                leftMax = Math.max(height[left], leftMax);
                sumRainVolume += Math.max(0, Math.min(leftMax, rightMax) - height[left]);
            } else {
                // 移动右指针，试图增加右边高度
                right--;
                rightMax = Math.max(height[right], rightMax);
                sumRainVolume += Math.max(0, Math.min(leftMax, rightMax) - height[right]);
            }
        }
        return sumRainVolume;
    }

    // 双指针 - Gemini
    public static int trap3(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int sumRainVolume = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    sumRainVolume += (leftMax - height[left]);
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    sumRainVolume += (rightMax - height[right]);
                }
                right--;
            }
        }
        return sumRainVolume;
    }


    public static void main(String[] args) {
        System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})); // 6
        System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5})); // 9
        System.out.println(trap(new int[]{5, 1, 7, 2, 6})); // 8
    }
}
